﻿/**
 * @file list.h
 * @author septem (jsm920@outlook.com)
 * @brief 相当于c++的 list<> 实现动态链表功能，数组可随push动态增大，所保存的数据不会因 push/pop 操作而发生在内存中移动的现象。
 * 但是 insert/erase/shrink 会可能会导致数据发生移动
 * @version 0.1
 * @date 2024-12-09
 * @note 概念：
 *  容器：可保存相同数据大小的结构体。
 *  变长容器：可以改变大小以适应不断增涨的数据的容器
 *  元素：保存在容器中的数据，同一个结构体中元素具有相同大小，并且分为元素大小和占用空间大小。
 *      元素在内存中的地址可能会向sizeof(void*)的整数倍取整。
 *  块：预分配的用于保存元素的内存块，使用链表方式管理。
 *  遍历：通过 listiterator_t 类函数遍历
 *  表头: list链表中第一个元素
 *  表尾: list链表中最后一个元素
 * @note 遍历 list_t 方法 请查看 struct listiterator_t 和 struct listnode_t
 * 
 * @note 20250206 准备删除 listblock_t ,改用预分配一个链表的思路,使用时从链表中取,删除是返回链表
 * @copyright Copyright (c) 2024
 * 
 */
#ifndef _HEAD_LIST_
#define _HEAD_LIST_
#if defined(_WIN32) && defined(_MSC_VER)
#include <stdio.h>
#include <malloc.h> // _malloca() 栈上分配空间的函数
#elif defined(__linux__)
#endif

#ifndef roundup
#if defined(_WIN32) && defined(_MSC_VER)
//对 x 向上取 y 的整数倍
#define  roundup(x, y) ((((x) + ((y) - 1)) / (y)) * (y))
#elif defined(__linux__)
//对 x 向上取 y 的整数倍
#define  roundup(x, y) 			    \
({							        \
	typeof(y) __y = y;				\
	(((x) + (__y - 1)) / __y) * __y;\
})
#endif
#endif
/**
 * @brief list链表的 节点信息,用于链接前后元素节点,
 * @note 遍历list_t方法
 * ```c
 *  // 向后遍历
 * for()
 * for(listnode_t* pln = ListNodeHead(pl); pln; pln=ListNodeNext(pln))
 * {
 *      sometype_t* p = (sometype_t*)ListNodeData(pln);
 *      // some code
 * }
 *  // 向前遍历
 * for(listnode_t* pln = ListNodeTail(pl); pln; pln=ListNodePrev(pln))
 * {
 *      sometype_t* p = (sometype_t*)ListNodeData(pln);
 *      // some code
 * }
 * ```
 */
typedef struct listnode_t
{
    struct listnode_t* plnPrev; // 前一个节点，当节点没有使用 plnPrev 和 plnNext 置为 LISTNODEUNUSED
    struct listnode_t* plnNext; // 后一个节点，当节点没有使用 plnPrev 和 plnNext 置为 LISTNODEUNUSED
}listnode_t;

#define ListNode(pdata) ((listnode_t*)((char*)pdata - sizeof(listnode_t))) //根据元素获取节点地址
#define ListNodeData(pln) (void*)((char*)(pln) + sizeof(listnode_t)) // 获取节点的元素数据
#define ListNodeHead(pl) ((pl)->plnHead) //获取链表的 表头
#define ListNodeTail(pl) ((pl)->plnTail) //获取链表的 表尾
#define ListNodeNext(pln) ((pln)->plnNext) //获取下一个链表
#define ListNodePrev(pln) ((pln)->plnPrev)  //获取前一个链表

/**
 * @brief 定义 预分配的 listnode_t* 块指针 用于 保存 ListRealloc 的节点
 * 
 */
#define listblock_t listnode_t* // 用于 保存 ListRealloc 的节点

#define LISTDEFAULTCNTBLOCK 8 // 默认分配的 listblock_t 块大小,
/**
 * @brief 可变长的链表容器结构
 * 
 */
typedef struct list_t
{
    struct listnode_t* plnHead; // 表头
    struct listnode_t* plnTail; //表尾
    struct listnode_t* plnPeralloc; //预分配的节点 cntCapacity - cntElem 就是 plnPeralloc的数量
    listblock_t* plbM;  //当 plb 不够用时 malloc一个空间用于保存 预分配的块的指针
    listblock_t plb[LISTDEFAULTCNTBLOCK];  // 保存预分配的块的指针，用于后续 free
    unsigned int cntCapacity; // list_t 当前能容下最大的元素的数量 
    unsigned int cntElem; // 已保存的元素数量
    unsigned int cntGrow;   // 预分配的块大小
    unsigned int szElem; // 每个元素实际大小
    unsigned int szNode; // 每个节点大小包含元素的大小,
    unsigned int cntPLBM;
    // 注意 ListInit 函数会在 后面 预分配 cntGrow 个 节点供使用
}list_t;

/**
 * @brief list 的 iterator 对标 stl中的list<>::iterator 用于 遍历所有list_t 中的元素
 * ```c
 * // 向前遍历
 * for(listiterator_t* pli = ListIteratorInit(pl,-1); pli != NULL; pli = ListIteratorPrev(pai) )
 * {
 *      sometype_t* p = (sometype_t*)ListIteratorDataPtr(pli);
 *      // some code
 * }
 * for(listiterator_t* pli = ListIteratorInit(pl,0); pli != NULL; pli = ListIteratorNext(pai) )
 * {
 *      sometype_t* p = (sometype_t*)ListIteratorDataPtr(pli);
 *      // some code
 * }
 * ```
 */
typedef struct listiterator_t
{
    list_t* pl;
    listnode_t* pln;
    unsigned int ser;
}listiterator_t;
#if defined(_WIN32) && defined(_MSC_VER)
/**
 * @brief 在栈上获取一个 listiterator_t* 配合 以下语句来循环遍历链表
 * 
 */
#define ListIteratorInit(pl, pos) ( ListIteratorInit2((listiterator_t*)_malloca(sizeof(listiterator_t)),(pl),(pos)))
#elif defined(__linux__)
/**
 * @brief 在栈上获取一个 listiterator_t* 配合 以下语句来循环遍历链表
 * 
 */
#define ListIteratorInit(pl, pos) ({listiterator_t li = {0};ListIteratorInit2(&li,(pl),(pos));})
#endif
/**
 * @brief 初始化一个 listiterator_t 结构体
 * 
 * @param pli 
 * @param pl 
 * @param pos 
 * @return listiterator_t* 
 */
listiterator_t* ListIteratorInit2(listiterator_t* pli, list_t* pl, int pos);

/**
 * @brief 向前移动一个节点
 * 
 * @param pli 
 * @return listiterator_t* 
 */
listiterator_t* ListIteratorPrev(listiterator_t* pli);

/**
 * @brief 向后移动一个节点
 * 
 * @param pli 
 * @return listiterator_t* 
 */
listiterator_t* ListIteratorNext(listiterator_t* pli);

/**
 * @brief 从 当前遍历的 listiterator_t 获取正在遍历的数据
 * @param pli 正在使用的 listiterator_t
 */
#define ListIteratorDataPtr(pli) (ListNodeData((pli)->pln))

/**
 * @brief 获取需要分配给 cnt 个 szElem大小元素的 list_t 对象的空间大小
 * 
 */
#define ListMemUsed(szElem, cnt) sizeof(list_t) + (roundup((sizeof(listnode_t)+(szElem)),sizeof(void*)))*(cnt)

/**
 * @brief 申请并初始化一个 list_t* 
 * 
 * @param szElem 
 * @param cnt 
 * @return list_t* 
 */
list_t* ListMalloc(unsigned int szElem, unsigned int cnt);

/**
 * @brief 初始化一个 list_t* 结构
 * 
 * @param pl 
 * @param szElem 
 * @param cnt 
 * @return list_t* 
 */
list_t* ListInit(list_t*pl ,unsigned int szElem, unsigned int cnt);

/**
 * @brief 注销一个 list_t* ，但不 free(pl)
 * 
 * @param pl 
 */
void ListUninit(list_t*pl);

/**
 * @brief 注销并Free一个 list_t*
 * 
 * @param pl 
 */
void ListFree(list_t*pl);

/**
 * @brief 再次分配一个新块
 * 
 * @param pl 
 * @param grow 
 * @return list_t* 
 */
int ListRealloc(list_t*pl, unsigned int grow);

/**
 * @brief 向 list_t* 尾部压入一个元素
 * 
 * @param pl 
 * @param data 
 * @return void* 
 */
void* ListPush(list_t*pl, void* data);

/**
 * @brief 从 list_t* 尾部弹出一个元素（不影响已有元素在内存中的位置）
 * 
 * @param pl 
 * @return listnode_t* 
 */
listnode_t* ListPop(list_t*pl);

/**
 * @brief 向 list_t* 头部压入一个元素（不影响已有元素在内存中的位置）
 * 
 * @param pl 
 * @param data 
 * @return void* 
 */
void* ListUnshift(list_t*pl, void* data);

/**
 * @brief 从 list_t* 头部弹出一个元素（不影响已有元素在内存中的位置）
 * 
 * @param pl 
 * @return listnode_t* 
 */
listnode_t* ListShift(list_t*pl);

/**
 * @brief 在 where 位置之前插入 cnt 个元素，当 where 是NULL时向尾部插入 cnt个元素（不影响已有元素在内存中的位置）
 * 
 * @param pl 
 * @param where 在 where 之前插入，必希是 pl 的元素指针或NULL 。 where 是NULL时向尾部插入 cnt个元素
 * @param data 不可为NULL
 * @param cnt 不可为0
 * @return listnode_t* 
 */
listnode_t* ListInsert(list_t* pl, listnode_t* where, void* data, unsigned int cnt);

/**
 * @brief 从 where （包括 where ）节点开始删除 cnt 个元素 （不影响已有元素在内存中的位置）
 * 
 * @param pl 
 * @param where 
 * @param cnt 
 * @return listnode_t* 返回删除元素之后的第一个节点
 */
listnode_t* ListErase(list_t* pl,listnode_t* where, unsigned int cnt);
/**
 * @brief 把 pln 移动到 where 之前，如果 where 为 NULL ，把 pln 移动到最后，
 * 
 * @param pl 
 * @param pln0 
 * @param pln1 
 * @return listnode_t* 
 */
listnode_t* ListMoveBefore(list_t* pl,listnode_t* where,listnode_t* pln);
/**
 * @brief 交换两个节点,pln0和pln1不能同时为NULL
 * 如果 pln0 为 NULL,那么把 pln1 交换到 pl->plnHead,
 * 如果 pln1 为 NULL,那么把 pln0 交换到 pl->plnTail,
 * 
 * @param pl 
 * @param pln0 
 * @param pln1 
 * @return listnode_t* 
 */
listnode_t* ListSwap(list_t*pl,listnode_t* pln0,listnode_t* pln1);

/**
 * @brief 在 pl 中查找 对应的数据，需传入查找函数 compar
 * 
 * @param pl 
 * @param ptr 
 * @param compar 
 * @return listnode_t* 
 */
listnode_t* ListSearch(list_t*pl, void* ptr, int (*compar)(const void*, const void*));
/**
 * @brief 获取 list_t* pl 的当前元素数量
 * @param pl list_t*
 * 
 */
#define ListSize(pl) ((pl)->cntElem)

/**
 * @brief 获取 list_t* pl 的当前可容下元素数量
 * @param pl list_t*
 * 
 */
#define ListCapacity(pl) ((pl)->cntCapacity)

/**
 * @brief 获取 list_t* pl 第一个元素
 * @param pl list_t*
 * 
 */
#define ListFront(pl) ((pl)->plnHead)

/**
 * @brief 获取 list_t* pl 最后一个元素
 * @param pl list_t*
 * 
 */
#define ListBack(pl) ((pl)->plnTail)

/**
 * @brief 获取 pos 位置的节点指针  超过范围返回NULL
 * 
 * @param pl 
 * @param pos 范围内 (-1-cntElem,-1]或 [0,cntElem)
 * @return listnode_t* 
 */
listnode_t* ListAt(list_t* pl, int pos);

/**
 * @brief 获取 pos 位置的节点指针  超过范围返回NULL
 * 
 * @param pl 
 * @param pos 
 * @return listnode_t* 
 */
listnode_t* ListAt2(list_t* pl, unsigned int pos);

#ifdef _DEBUG
void list_print_positive_order_int(list_t* pl);
void list_print_negative_order_int(list_t* pl);
void list_print_int_by_iterator(list_t* pl);
#endif

#endif // end of define _HEAD_LIST_